next up previous index
Next: Justification Up: Dijkstra's algorithm Previous: Initialisation   Index

The iterative step

The iterative step of the algorithm is now as follows:
While $S^{\ast}-S$ is not empty:
D1:
pick any $v \in S^{\ast}-S$ such that $D(v) \leq D(u)$ for all $u \in S^{\ast}-S$;
D2:
extend $S$ to $S \cup \{v\}$;
D3:
redefine the function $D$ on $(S\cup \{v\})^{\ast}$ as follows:
(a)
if $w \in S \cup \{v\}$, leave $D(w)$ unchanged;
(b)
otherwise, if $w$ is not adjacent to $v$, leave $D(w)$ unchanged;
(c)
otherwise, if $D(w)$ was not previously defined, set $D(w)$ equal to the sum of $D(v)$ and the length of the shortest arc from $v$ to $w$;
(d)
otherwise, set $D(w)$ to be the smaller of the old value of $D(w)$ and the sum of $D(v)$ and the length of the shortest arc from $v$ to $w$.



Peter Williams 2002-06-07